1. Field of the Invention
The present invention relates to cryptanalysis and, more particularly, relates to methods for “cracking”, or deciphering, cryptosystems, by analyzing one or more erroneous outputs to infer information ordinarily difficult or impossible for a party not privy to secret information. Knowing how a cryptosystem may be cracked suggests methods for avoiding attacks on the cryptosystem, thus further improving the integrity of the cryptosystem. A security expert or cryptosystem designer may use the inventive methods in the design of cryptography devices to verify that an existing or proposed device is impervious to such attacks.
2. Discussion of Related Art
Cryptography has become essential to the acceptance of electronic commerce and sensitive electronic communications. For example, secure digital signatures and verification methods provide high assurance that a party is who it represents itself to be. This assurance is vital to the general acceptance of, for example, commerce over the Internet, the use of electronic money, cellular communications, and remote computer login procedures. Typically, certain well-known cryptographic methods are used to encrypt information in a manner that is very difficult to decrypt without certain secret information, thus making these signatures and verifications secure. One type of cryptographic method which is commonly used is public key cryptography.
1. Public Key Cryptography
In a typical public key cryptographic system, each party i has a public key (or exponent) Pi and a secret key (or exponent) Si. The public key Pi, is known to everyone, but the secret key Si is known only to party i. A plain text message m to user i is encrypted to form the cipher text message x using a public operation P which makes use of the public key Pi known to everyone, i.e., x=P(m,Pi). The cipher text message x is decrypted using a secret operation S which makes use of the secret key Si, i.e., m=S(x,Si). Only party i who has the secret key Si can perform the secret operation to decrypt the encrypted message x to obtain clear text message m.
Public key cryptographic techniques may be used for authentication. Authentication is a (theoretically) fool-proof technique for a party to verify that a party contacting it is the party is asserts to be. For example, a confidential network may require that a party authenticate itself before gaining access to the network.
If it is true that P(S(x,Si),Pi)=x (recall the S(x,Si)=m, resulting in P(m,Pi)=x), then the owner of the corresponding keys Pi, Si could sign message m by producing E=S(m,Si), where E indicates the signature. The verifier, given x and E, will verify x=P(E,Pi). One type of a cryptography system could be used for verification as follows: challenge the party claiming to be i with message x and ask the party to sign the message x using his secret key Si, then verify the signature using Pi. More efficient and secure authentication protocols may be used, such as the Fiat-Shamir and Schnorr protocols discussed below.
FIG. 1A is a block diagram of a typical cryptography device 100. The device 100 has a processor 102 including one or more CPUs 102, a main memory 104, a disk memory 106, an input/output device 108, and a network interface 110. The devices 102-110 are connected to a bus 120 which transfers data, i.e., instructions and information between each of these devices 102-110.
FIG. 1B illustrates a network 150 over which cryptography devices 100 may communicate. Two or more cryptography devices 100, 100′ may be connected to a communications network 152, such as a wide area network; which may be the Internet, a telephone network, or leased lines; or a local area network. Each device 100 may include a modem 154 or other network communication device to send encrypted messages over the communications network 152. A cryptography device 100 may be a gateway to a sub-network 156. That is, the device 100 may be an interface between a wide area network 152 and a local area (sub) network 156.
An example of a public key cryptographic technique which may be performed by the device 100 is the well known RSA technique. In accordance with this technique, a party i has stored in memory 104 or 106 its own public key (or exponent) ei and modulus N (where N is a product of two large prime numbers p,q) and a secret key in the form of an exponent si. It has stored or otherwise obtained the public key e; of a party to which it wishes to send a message. The party may have a plain text message m which it wishes to send to party j without others knowing the content of m. The device 100 encrypts the message m to form x=me; mod N using processor 102 and perhaps software stored in main memory 104. Party j's device can then decrypt x to obtain m by performing the operation m=Xs,j mod N.
Another public key cryptographic technique is the Rabin modular square root. In this technique, the secret operation involves obtaining a modular square root and the public operation involves a modular squaring operation.
Rabin's Signature Scheme is similar to the RSA signature system and relies on the difficulty of factoring for its security. As above, assume N=pq is a product of two large prime numbers p,q. To sign a document D, party i's device 100 first hashes D to a number D′ between 1 and N. The signer's device 100, which knows the secret factorization of the modulo N, computes the square root of D′ (mod N) using the processor 102. Thus, the signature E is:E=√{square root over (D′)}(mod N)  (1)Without knowing the factorization of N, computing the modular square root of a number is difficult.
The Fiat-Shamir authentication scheme is a cryptosystem for a first party to authenticate its identity to another party. This is done as follows: party i's cryptography device 100 and party j's cryptography device 100′ (as seen in FIG. 1B) agree on an n-bit modulus N=pq, where p and q are each a large prime number. Party i's secret keys are a set of invertible elements (i.e., bits) s1, . . . , st (mod N) stored in the memory 104 or 106 of its cryptography device 100. Party i's public key is the square of these invertible elements (bits) v1=s12, . . . , vt=st2 (mod N). Party i authenticates itself to party j using the following protocol:                1. Party i's cryptography device selects a random r, generates r2 mod N, and transmits this value to party j's cryptography device.        2. Party j's cryptography device selects a random subset S⊂ (1, . . . , t), and transmits the subset to party i via an I/O.        3. Party i's cryptography device computes y=Πiεssi mod N and transmits y to party j.        4. Party j's device verifies party i's identity by checking that y2=r2Πjεsvj(mod N).        
The Schnorr authentication scheme is another cryptosystem for a first party to authentic its identity to a second party. The security of the Schnorr authentication scheme is based on the difficulty of computing discrete log modulo a prime. In Schnorr's authentication scheme, party i and party j agree on a prime number p and a generator g of Zp+. where Zp+ is group of integers modulo p and relatively prime to p. Party i chooses a secret integer si and publishes yi=gsi mod p as party i's public key. Party i authenticates itself to party j by engaging in the following protocol:                1. Party i's cryptography device selects a random integer r ε[0,p] and sends z=gt mod p to party j's cryptography device via an I/O 210.        2. Party j's cryptography device selects a random integer tε[0, T] and sends t to party i via an I/O. Here, T<p is an upper bound chosen beforehand.        3. Party i's device sends u=r+ts mod p−1 to party j's device.        4. Party j's device verifies that gu=zyt mod p.        
Cryptography schemes such as Schnorr have the property that if two distinct messages are signed using the same random element (e.g., r), then the secret key of the signer can be computed by anyone having the messages, the signatures, and public information such as the public key of the signer.
2. Prior Art Difficulties Cracking Cryptosystems
Cracking the RSA public key cryptosystem, and several other cryptosystems, is difficult because it typically requires that the modulus be factored (or other operation of comparable complexity). This is particularly difficult. It takes thousands of hours of computing time to factor a 512 bit modulus. RSA currently uses a 512 bit modulus, but it is expected that this may be upgraded in the future to a 1024 bit modulus. However, if the modulus may be determined without significant factoring, the computing time may be greatly reduced and the security of the cryptosystem compromised.
In an article “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,” Proc. of Crypto '96, P. Kocher proposes that a few bits of a modulus may be obtained by the amount of time certain operations took to be performed. This allowed the cryptosystem to be cracked without factoring. The drawbacks of this method are (1) it requires very precise timing of the length of time taken to perform certain calculations; and (2) it requires a large number of samples.
3. Reasons For Cracking A Cryptosystem
The availability of electronic commerce and certain electronic communications depend on difficult-to-crack cryptosystems to prevent unauthorized access to the secured information. If, for example, an adversary obtains a party's secret key, the adversary could electronically forge the party's signature without the party's knowledge. As another example, the adversary could present itself to third parties as the party whose secret key was obtained. Moreover, once obtained, the secret key may be duplicated and shared with others. Thus, it is vitally important that the cryptosystem used to protect important information be difficult to crack.
A threat model for cracking a cryptosystem is useful because it verifies whether a cryptosystem or cryptography device is vulnerable to that attack. If so, the system or device is no longer considered to be secure. This is true because in the cryptography community, the mere possibility of an attack on a cryptosystem is universally accepted as very serious. Security experts must assume that the cryptosystem is no longer safe from adversaries. Thus, a method for cracking cryptosystems is an exceptionally useful tool for security experts and cryptosystem designers testing existing cryptosystems and developing new cryptosystems. The cracking method may be applied to an existing or a proposed system to verify that the system is impervious to the attack. Thus, the cracking method may also be used to design cryptosystems impervious to the attack.
Therefore, it is an object of the present invention to provide a method for cracking the public key signature cryptosystems without factoring the modulus.
It is another object of the present invention to provide a method for cracking cryptosystems which uses the Chinese Remainder Theorem.
It is yet a further object of the present invention to provide a method for cracking authentication cryptosystems.
It is yet another object of the present invention to use transient errors in encrypted data to determine secret information.
It is yet a further object of the present invention to provide methods for testing the security of a cryptosystem.
It is a further object of the present invention to provide a method for providing a cryptosystem and/or cryptography device impervious to cracking due to transient hardware faults.